home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / cocktail.txt < prev    next >
Text File  |  1993-07-24  |  20KB  |  469 lines
  1. *************************************************************************
  2. *                                                                       *
  3. *  Compiler Construction Tool Box                                       *
  4. *  ==============================                                       *
  5. *                                                                       *
  6. *  Version 9209                                                         *
  7. *                                                                       *
  8. *  Copyright (c) 1989, 1990, 1991, 1992 by                              *
  9. *                                                                       *
  10. *  Gesellschaft fuer Mathematik und Datenverarbeitung                   *
  11. *  (German National Research Center for Computer Science)               *
  12. *  Forschungsstelle fuer Programmstrukturen                             *
  13. *  an der Universitaet Karlsruhe                                        *
  14. *                                                                       *
  15. *  All rights reserved. GMD assumes no responsibility for the use       *
  16. *  or reliability of its software.                                      *
  17. *                                                                       *
  18. *************************************************************************
  19.  
  20.  
  21. Direct requests, comments, questions, and error reports to:
  22.  
  23.    Josef Grosch
  24.    GMD Forschungsstelle
  25.    Vincenz-Priessnitz-Str. 1
  26.    D-7500 Karlsruhe 1
  27.    Phone: +721-662226
  28.    Email: grosch@karlsruhe.gmd.de
  29.  
  30.  
  31. Distribution Format:
  32. --------------------
  33.  
  34. The compiler construction tool box is available via anonymous ftp from
  35. several file servers:
  36.  
  37. host                     number        directory
  38.  
  39. ftp.karlsruhe.gmd.de     192.76.241.33 /pub/cocktail
  40. ftp.gmd.de               129.26.8.90   /gmd/cocktail
  41. iraun1.ira.uka.de        129.13.10.90  /pub/programming/cocktail
  42. ftp.rus.uni-stuttgart.de 129.69.1.12   /soft/unix/programming/compilerbau
  43. ftp.th-darmstadt.de      130.83.55.75  /pub/programming/languages/compiler-compiler/cocktail
  44. ftp.eb.ele.tue.nl                      /pub/src/cocktail
  45. src.doc.ic.ac.uk         146.169.2.1   /languages/tools/gmd
  46. gatekeeper.dec.com                     /.3/plan/gmd
  47.  
  48.  
  49. The files or file trees are compressed: For UNIX tar and compress are used
  50. (suffix: .tar.Z), for MSDOS zip is used (suffix: .zip).
  51.  
  52. To uncompress a file tree use:
  53.  
  54.    uncompress < tool.tar.Z | tar xvf -   or   unzip tool.zip
  55.  
  56.  
  57. Alternatively, the toolbox is distributed on tape in uncompressed tar format
  58. on the following media:
  59.  
  60. - DC300/600 data cartridge (streamer tape) 
  61. - TK 50
  62. - Exabyte
  63. - 1/2" magnetic tape (1600 bpi)
  64.  
  65. To read a tape use:
  66.  
  67.    tar -xvfb /dev/rst0 20   or   tar -xvb 20   or similar commands
  68.  
  69.  
  70. The directories and their contents are as follows:
  71. --------------------------------------------------
  72.  
  73. directory       contents
  74. ------------------------------------------------------------------------
  75. README          this file
  76. Makefile        compilation, installation, and test of the tools (UNIX)
  77. compile.bat     compilation  of the tools (MSDOS)
  78. install.bat     installation of the tools (MSDOS)
  79. test.bat        test         of the tools (MSDOS)
  80. doc.ps          documentation in postscript format
  81. doc.me          documentation in troff format, me macros
  82. doc.doc         documentation in ascii format (without pictures)
  83. man             manual pages  in troff format, man macros
  84. rex             Scanner Generator
  85. lalr            LALR(1) Parser Generator
  86. ell             LL(1) Recursive Descent Parser Generator
  87. bnf             Transforms Grammars from Extended BNF to Plain BNF
  88. front           Common Front-End of Lalr, Ell, and Bnf
  89. reuse           Library of Reusable Modules (needed for all programs)
  90. common          Library for estra and ell
  91. specs           Example Specifications for the Above Tools
  92. cg              Common Program implementing Ast and Ag
  93.                 Ast = Generator for Abstract Syntax Trees
  94.                 Ag  = Attribute Evaluator Generator
  95. puma            Transformation Tool based on Pattern Matching
  96. l2r             Transforms Lex  input to Rex  input
  97. y2l             Transforms Yacc input to Lalr input
  98. r2l             Transforms Rex  input to Lex  input
  99. rpp             Rex PreProcessor: rpp + cg extract most of a scanner
  100.                 specification out of a parser specification
  101. estra           Transformation of attributed trees (prototype)
  102. hexa            contains the scanner and parser tables of Rex and Front
  103.                 (= front-end of Lalr and Bnf) converted from binary to
  104.                 ascii hexadecimal representation
  105. dos        directory containg the MSDOS version
  106. bin             UNIX: shell scripts (my version), MSDOS: batch scripts
  107. lib             executables, table and data files (for SUN 3/SunOS 4.0 or PC/MSDOS)
  108. (mtc            Modula-2 to C translator)
  109.  
  110. The names of the subdirectories indicate the following types of information:
  111.  
  112. sub directory   contents
  113. ------------------------------------------------------------------------
  114. src             source files in Modula-2
  115. m2c             source files in C (generated from the Modula-2 sources)
  116. src             source files in C (generated from the C sources for MSDOS)
  117. c               source files in C (hand-written)
  118. lib             data files, module skeletons
  119. test            test environment for a tool
  120.  
  121.  
  122. Documentation:
  123. --------------
  124.  
  125. The directories doc.ps, doc.me, and doc.doc contain documentation in postscript
  126. format, troff format (me macros), and in ASCII format (without pictures).
  127. The documentation for UNIX and MSDOS is the same. Therefore the documents are
  128. stored in the UNIX directory, only, they are not repeated in the 'dos' subdirectory.
  129. The document entitled "Toolbox Introduction" in the files intro.ps, intro.me,
  130. or intro.doc gives an overview and introduces into the toolbox. It should be
  131. read first. The following documents are available:
  132.  
  133. Filename        Title
  134. ------------------------------------------------------------------------
  135. intro           Toolbox Introduction
  136. toolbox         A Tool Box for Compiler Construction
  137. werkzeuge       Werkzeuge fu"r den U"bersetzerbau
  138. reuse           Reusable Software - A Collection of Modula-2-Modules
  139. prepro          Preprocessors
  140. rex             Rex - A Scanner Generator
  141. scanex          Selected Examples of Scanner Specifications
  142. scangen         Efficient Generation of Table-Driven Scanners
  143. lalr-ell        The Parser Generators Lalr and Ell
  144. lalr            Lalr - A Generator for Efficient Parsers
  145. ell             Efficient and Comfortable Error Recovery in Recursive
  146.                    Descent Parsers
  147. highspeed       Generators for High-Speed Front-Ends
  148. autogen         Automatische Generierung effizienter Compiler
  149. ast             Ast - A Generator for Abstract Syntax Trees
  150. toolsupp        Tool Support for Data Structures
  151. ag              Ag - An Attribute Evaluator Generator
  152. ooags           Object-Oriented Attribute Grammars
  153. estra           Spezifikation und Implementierung der Transformation
  154.                    attributierter Ba"ume
  155. puma            Puma - A Generator for the Transformation of Attributed Trees
  156. trafo           Transformation of Attributed Trees Using Pattern Matching
  157. (minilax        Specification of a MiniLAX-Interpreter)
  158. (begmanual      BEG - a Back End Generator - User Manual)
  159.  
  160.  
  161. References:
  162. -----------
  163.  
  164. 1.   J. Grosch, `Generators  for  High-Speed  Front-Ends',  LNCS,
  165.      371, 81-92 (Oct. 1988), Springer Verlag.
  166.  
  167. 2.   H. Emmelmann, F. W. Schroeer, Rudolf Landwehr, ` BEG - a Generator
  168.      for Efficient Back Ends', Sigplan Notices, 24, 227-237 (Jul. 1989)
  169.  
  170. 3.   W. M. Waite, J. Grosch and F. W.  Schroeer,  `Three  Compiler
  171.      Specifications', GMD-Studie Nr. 166, GMD Forschungsstelle an
  172.      der Universitaet Karlsruhe, Aug. 1989.
  173.  
  174. 4.   J. Grosch,  `Efficient  Generation  of  Lexical  Analysers',
  175.      Software-Practice & Experience, 19, 1089-1103 (Nov. 1989).
  176.  
  177. 5.   J. Grosch, `Efficient and Comfortable Error Recovery in Recursive
  178.      Descent Parsers', Structured Programming, 11, 129-140 (1990).
  179.  
  180. 6.   J. Grosch, H. Emmelmann, `A Tool Box for Compiler Construction',
  181.      LNCS, 477, 106-116 (Oct. 1990), Springer Verlag.
  182.  
  183. 7.   J. Grosch, `Object-Oriented Attribute Grammars', in: Proceedings of the
  184.      Fifth International Symposium on Computer and Information Sciences (ISCIS V)
  185.      (Eds. A. E. Harmanci, E. Gelenbe), Cappadocia, Nevsehir, Turkey, 807-816,
  186.      (Oct. 1990).
  187.  
  188. 8.   J. Grosch,  `Lalr - a Generator for Efficient Parsers',
  189.      Software-Practice & Experience, 20, 1115-1135 (Nov. 1990).
  190.  
  191. 9.   J. Grosch, `Tool Support for Data Structures',
  192.      Structured Programming, 12, 31-38 (1991).
  193.  
  194. 10.  J. Grosch, `Transformation of Attributed Trees Using Pattern Matching',
  195.      to appear (1992).
  196.  
  197.  
  198. Machine Dependencies:
  199. ---------------------
  200.  
  201. All machine dependent code is isolated in the file System.c which is written
  202. in C. This file is set up to work under UNIX and MSDOS. There are three
  203. copies of this file in the following directories:
  204.  
  205.    reuse/c
  206.    reuse/src
  207.    reuse/m2c
  208.  
  209. The UNIX command 'install' is used during installation. Unfortunately, this
  210. command is not as standard as it should be. If 'install' is missing on your
  211. machine or it complains about the calls then the shell script in the file
  212. hexa/install can simulate the desired behaviour.
  213.  
  214.  
  215. Installation under UNIX:
  216. ------------------------
  217.  
  218. The Makefile at the global level controls the compilation and installation
  219. of the individual tools. It activates the tool specific Makefiles.
  220.  
  221. Several tools use binary data files called Scan.Tab and Pars.Tab whose internal
  222. representation depends on whether the machine is little-endian or big-endian.
  223. All machines store integer numbers in a sequence of bytes with increasing adresses.
  224. An integer number usually consists of four bytes where the bytes at both ends are
  225. termed most significat byte (MSB) and least significant byte (LSB). Big-endian
  226. machines store the MSB at the lowest address and the LSB at the highest address.
  227. Little-endian machines store the bytes the other way round.
  228. Big-endian are e. g. MC 680x0, SUN/3, SUN/4, SPARC,
  229. little-endian are e. g. VAX, DEC Station, 80386, 80486.
  230.  
  231. Initially the binary data files are configured for big-endian machines.
  232. To find out in which class your machine is in execute:
  233.  
  234.    make endian
  235.  
  236. To convert the binary files from big-endian to little-endian or vice versa execute:
  237.  
  238.    make bin.conv
  239.  
  240. Edit the first couple of lines in the Makefile to accomodate your needs.
  241. To compile the programs execute:
  242.  
  243.    make
  244.  
  245. To install the programs execute:
  246.  
  247.    make install
  248.  
  249.  
  250. Installation under MSDOS:
  251. -------------------------
  252.  
  253. Requirements to run the binaries:
  254.  
  255.    - 80386 or 80486 CPU
  256.    - at least 2 MB memory
  257.    - DOS extender (go32, from DJ Delorie)
  258.  
  259. Requirements to compile the sources:
  260.  
  261.    - GNU C compiler (gcc, DJ Delorie's GCC port to DOS)
  262.    - GNU make (called gmake on our machine)
  263.    - ar and ranlib (archive handling)
  264.  
  265. The software of DJ Delorie's GCC port to DOS is available from:
  266.  
  267.     host:      grape.ecs.clarkson.edu
  268.     login:     ftp
  269.     directory: /pub/djgcc
  270.  
  271.  
  272. Installation from the sources:
  273.  
  274. There are several batch files at the global level for compilation and installation
  275. of the individual tools. These activate either tool specific batch files or
  276. GNU make (gmake) which is controlled by tool specific Makefiles.
  277.  
  278. Define four environment variables describing two directories that will store the
  279. batch files that control the tools and the binaries and data files of the tools.
  280. UBIN and ULIB hold the same names as BIN and LIB but use the UNIX style
  281. (/ instead of \). For example:
  282.  
  283.    set BIN=\usr\hacker\bin
  284.    set LIB=\usr\hacker\lib
  285.    set UBIN=/usr/hacker/bin
  286.    set ULIB=/usr/hacker/lib
  287.  
  288. To compile the programs execute:
  289.  
  290.    compile.bat
  291.  
  292. To install the programs execute:
  293.  
  294.    install.bat
  295.  
  296. To test the programs execute:
  297.  
  298.    test.bat
  299.  
  300.  
  301. Installation of the binaries:
  302.  
  303. Copy the directories bin and lib to an appropriate location and set up the
  304. four environement variables as described above. That's it. To test the programs
  305. execute:
  306.  
  307.    test.bat
  308.  
  309.  
  310. Recent Changes
  311. --------------
  312.  
  313. Version 9209:
  314.  
  315. - Port to MSDOS.
  316.  
  317. Version 9208:
  318.  
  319. - The scanner generator 'rex' and the parser generators 'lalr' and 'ell'
  320.   allow to chose arbitrary names for the generated modules. Therefore, it is
  321.   possible to have several scanners and parsers in one program.
  322.  
  323. - The length of a token and the lookahead in scanners generated by 'rex' is no
  324.   longer restricted to 256 characters. Both, tokens and lookahead can be of
  325.   arbitrary length. A restriction in the size of the tables generated by 'lalr'
  326.   has been removed. Now it is possible to generate rather huge parsers.
  327.  
  328. - The attribute grammar tool 'ag' has been extended to generate attribute
  329.   evaluators for well-defined attribute grammars (WAGs). The program checks
  330.   grammars whether they obey this property. It is possible to access
  331.   non-local attributes and to compute attributes on a restricted form of
  332.   graphs.
  333.  
  334. - The auxiliary modules 'Errors' and 'Source' have been included into the
  335.   library of reusable modules called 'reuse'. The 'Errors' module has been
  336.   extended to support messages with a string argument. It allows to store
  337.   the messages and print them sorted by the source position. An extra module
  338.   named 'Positions' has been introduced in 'reuse', too, for the handling of
  339.   source positions.
  340.  
  341. - The program 'cg' which implements 'ast' and 'ag' accepts several input files.
  342.   Instead of one file that communicates a tree definition to 'puma' with the
  343.   fixed name 'TREE.TS' it is possible to produce several of those with different
  344.   names. This is of interest if different "views" have to be communicated.
  345.  
  346. - The extern declarations for malloc, free, and exit have been removed from
  347.   the generated C code.
  348.  
  349. - All tools do not generate # line directives by default, only upon request.
  350.  
  351. - In case of fatal errors during the execution of generated modules a user
  352.   defined exception routine can be called instead of the predefined 'exit (1)'.
  353.  
  354. Version 9202:
  355.  
  356. - The Toolbox contains a new tool for the transformation of attributed trees
  357.   called 'puma'. It is based on pattern-matching. It replaces its predecessor
  358.   'estra' and comes with documentation in English.
  359.  
  360. - The tool for abstract syntax trees 'ast' has been extended from single to
  361.   multiple inheritance. So-called "subunits" allow the implementation of one
  362.   abstract tree by several compilation units. The concept of "views" makes
  363.   it possible to derive from a common specification several abstract syntax
  364.   trees which represent subsets.
  365.  
  366. - The attribute grammar tool 'ag' has analogously been extended to process
  367.   object-oriented attribute grammars with multiple inheritance. It supports the
  368.   generation of several attribute evaluators that run one after the other.
  369.  
  370. - The error handling module for the parser generators 'lalr' and 'ell' are
  371.   independent of the parser module or the grammar. The manual for these parser
  372.   generators has been completely rewritten.
  373.  
  374. - The Modula-2 to C translator 'mtc' has a new code-generator. This brings
  375.   big efficiency improvements: 30% smaller program, 10% faster, 75% less
  376.   dynamic memory consumption. It generates ANSI C as well as K&R C.
  377.   
  378. - The sources of all tools are in ANSI C as well as in K&R C.
  379.  
  380. - All tools generate modules in the target languages C (ANSI + K&R), C++,
  381.   and Modula-2.
  382.  
  383. - The interface to the operating system has been redesigned. It allows to
  384.   switch IO operations between UNIX system calls and C library calls.
  385.   This should assure much better portability.
  386.   
  387.  
  388.  
  389.               Compiler Construction Tool Box
  390.               ==============================
  391.  
  392.      Rex (Regular EXpression tool) is a scanner  generator  whose
  393. specifications  are  based  on  regular expressions and arbitrary
  394. semantic actions written in one of  the  target  languages  C  or
  395. Modula-2.  As  scanners sometimes have to consider the context to
  396. unambiguously recognize a token the right context can  be  speci-
  397. fied by an additional regular expression and the left context can
  398. be handled by so-called  start  states.  The  generated  scanners
  399. automatically  compute the line and column position of the tokens
  400. and offer an efficient mechanism  to  normalize  identifiers  and
  401. keywords  to upper or lower case letters. The scanners are table-
  402. driven and run at a speed of 180,000 to 195,000 lines per  minute
  403. on a MC 68020 processor.
  404.  
  405.      Lalr is a LALR(1) parser generator accepting grammars  writ-
  406. ten  in  extended BNF notation which may be augmented by semantic
  407. actions expressed by statements of the target language. The  gen-
  408. erator  provides  a  mechanism  for  S-attribution,  that is syn-
  409. thesized attributes can be computed during parsing.  In  case  of
  410. LR-conflicts  unlike  other tools Lalr provides not only informa-
  411. tion about an internal state consisting of a set of items but  it
  412. prints a derivation tree which is much more useful to analyze the
  413. problem. Conflicts can be resolved by specifying  precedence  and
  414. associativity of operators and productions. The generated parsers
  415. include automatic  error  recovery,  error  messages,  and  error
  416. repair.  The  parsers  are  table-driven  and  run  at a speed of
  417. 560,000 lines per minute. Currently parsers can be  generated  in
  418. the target languages C and Modula-2.
  419.  
  420.      Ell is a LL(1) parser generator accepting the same  specifi-
  421. cation  language  as  Lalr except that the grammars must obey the
  422. LL(1) property. It  is  possible  to  evaluate  an  L-attribution
  423. during parsing. The generated  parsers  include  automatic  error
  424. recovery,  error  messages,  and  error  repair  like  Lalr.  The
  425. parsers are implemented following the  recursive  descent  method
  426. and  reach a speed of 810,000 lines per minute. The possible tar-
  427. get languages are again C and Modula-2.
  428.  
  429. Ast - A Generator for Abstract Syntax Trees
  430.  
  431. - generates abstract data types (program modules) to handle trees
  432. - the trees may be attributed
  433. - besides trees graphs are handled as well
  434. - nodes may be associated with arbitrary many attributes of arbitrary type
  435. - specifications are based on extended context-free grammars
  436. - common notation for concrete and abstract syntax
  437. - as well as for attributed trees and graphs
  438. - an extension mechanism provides single inheritance
  439. - trees are stored as linked records
  440. - generates efficient program modules
  441. - generates modules in Modula-2 or C
  442. - provides many tree operations (procedures):
  443. - node constructors combine aggregate notation and storage management
  444. - ascii graph reader and writer
  445. - binary graph reader and writer
  446. - reversal of lists
  447. - top down and bottom up traversal
  448. - interactive graph browser
  449.  
  450. Ag - An Attribute Evaluator Generator
  451.  
  452. - processes ordered attribute grammars (OAGs)
  453. - processes higher order attribute grammars (HAGs)
  454. - operates on abstract syntax
  455. - is based on tree modules generated by Ast
  456. - the tree structure is fully known
  457. - terminals and nonterminals may have arbitrary many attributes
  458. - attributes can have any target language type
  459. - allows tree-valued attributes
  460. - differentiates input and output attributes
  461. - allows attributes local to rules
  462. - allows to eliminate chain rules
  463. - offers an extension mechanism (single inheritance)
  464. - attributes are denoted by unique selector names
  465.    instead of nonterminal names with subscripts
  466. - attribute computations are expressed in the target language
  467. - attribute computations are written in a functional style
  468. - attribute computations can call external functions
  469. - non-functiona